﻿package fflib.container
{
	import fflib.utils.ArrayUtil;
	
	use namespace iterator;
	
	/**
	 * Einfach verkettete Liste.
	 * 
	 * Letzte Änderung: 10.08.2008
	 */
	public final class SLinkedList implements IContainer, IIterable
	{
		/**
		 * @private (iterator)
		 */
		iterator var p_first: SLinkedListNode;
		
		/**
		 * @private (iterator)
		 */
		iterator var p_last:  SLinkedListNode;
		
		/**
		 * @private
		 */
		private var p_node: SLinkedListNode;
		
		/**
		 * @private
		 */
		 private var p_size: int = 0;
				
		/**
		 * Gibt das erste Item in der Liste zurück, ohne es dabei zu entfernen.<br />
		 * Falls die Liste leer ist wird <code>null</code> zurück gegeben.
		 * 
		 * @return Die Daten des ersten Items.
		 * 
		 * @see #last()
		 */
		public function first(): * {
			if (this.isEmpty())
				return null;
			else
				return p_first.data;
		}
		
		/**
		 * Gibt das letzte Item in der Liste zurück, ohne es dabei zu entfernen.<br />
		 * Falls die Liste leer ist wird <code>null</code> zurück gegeben.
		 * 
		 * @return Die Daten des letzten Items.
		 * 
		 * @see #first()
		 * @see #pop()
		 */
		public function last(): * {
			if (this.isEmpty())
				return null;
			else
				return p_last.data;		
		}
		
		/**
		 * Gibt einen Iterator für diese Liste zurück.<br />
		 * Neu hinzugefügte Items können auch mit einer früheren
		 * erstellten Instanz durchiteriert werden.
		 * 
		 * @return Den Iterator.
		 */
		public function getIterator(): IIterator { return new SListIterator(this); }
		
		/**
		 * Fügt für jeden übergebenen Parameter ein neues Item hinten an die Liste hinzu.
		 * 
		 * @param args
		 * 
		 * @see #add()
		 * @see #push()
		 * @see #prepend()
		 */
		public function append(... args): void {
			var n: int = args.length;
			var i: int;
			
			for (i = 0; i < n; i++)
				this.add(args[i]);
		}
		
		/**
		 * Fügt für jeden übergebenen Parameter ein neues Item vorne an die Liste hinzu.<br />
		 * Dabei werden die Items in der gleichen Reihenfolge hinzugefügt, in der sie übergeben worden sind.
		 * 
		 * @param args
		 * 
		 * @see #add()
		 * @see #push()
		 * @see #append()
		 */
		public function prepend(... args): void {
			var n: int = args.length;
			var i: int;
			
			for (i = 0; i < n; i++)
				this.push(args[i]);
		}
		
		/**
		 * Fügt ein neues Item an das Ende der Liste.
		 * 
		 * @param value Der Wert des Items.
		 * 
		 * @see #push()
		 * @see #addAt()
		 * @see #pushAt()
		 */
		public function add(value: *): void {
			p_node = new SLinkedListNode(value);
			p_size++;
			
			if (!p_first)
				p_first = p_last = p_node;
			else {
				p_last.next = p_node;
				p_last      = p_node;
			}
		}
		
		/**
		 * Fügt eine neues Item nach der Position <code>index</code> ein.<br />
		 * Falls <code>index</code> außerhalb des maximalen bzw. minimalen Bereiches liegt,
		 * wird eine Exception geworfen.<br /><br />
		 * Zum Anfügen an den Anfang und das Ende der Liste muss List::add und List::push benutzt werden.
		 * 
		 * @param index Die Position, nach der das neue Item eingefügt wird.
		 * @param value Der Wert des Items.
		 * 
		 * @see #add()
		 * @see #push()
		 * @see #pushAt()
		 */
		public function addAt(index: int, value: *): void {
			if (index < 0 || index > p_size - 2)
				throw new Error("Index out of range!");
			
			var itr:  SListIterator   = this.getIterator() as SListIterator;
			var node: SLinkedListNode = new SLinkedListNode(value);
			
			itr.position = index;
			p_node       = itr.p_node;
			node.next    = p_node.next;
			p_node.next  = node;
		}
		
		/**
		 * Fügt ein neues Item an den Anfang der Liste.
		 * 
		 * @param value Der Wert des Items.
		 * 
		 * @see #add()
		 * @see #addAt()
		 * @see #pushAt()
		 */
		public function push(value: *): void {
			p_node = new SLinkedListNode(value);
			p_size++;
			
			if (!p_first)
				p_first = p_last = p_node;
			else {
				p_node.next = p_first;
				p_first     = p_node;
			}
		}
		
		/**
		 * Fügt eine neues Item vor der Position <code>index</code> ein.<br />
		 * Falls <code>index</code> außerhalb des maximalen bzw. minimalen Bereiches liegt,
		 * wird eine Exception geworfen.<br /><br />
		 * Zum Anfügen an den Anfang und das Ende der Liste muss List::add und List::push benutzt werden.
		 * 
		 * @param index Die Position, vor der das neue Item eingefügt wird.
		 * @param value Der Wert des Items.
		 * 
		 * @see #add()
		 * @see #push()
		 * @see #addAt()
		 */
		public function pushAt(index: int, value: *): void { this.addAt(index - 1, value); }
		
		/**
		 * Entfernt das Liste Item der Liste und gibt dieses zurück.<br />
		 * Falls die Liste leer ist wird <code>null</code> zurück gegeben.
		 * 
		 * @return Das entfernte Item.
		 * 
		 * @see #clear()
		 */
		public function pop(): * {
			if (this.isEmpty())
				return null;
			
			if (p_size < 2) {
				p_node  = p_first;
				p_first = p_last = null;
			}
			else {
				var itr: SListIterator = this.getIterator() as SListIterator;
				p_node = p_last;
				
				itr.position = itr.end() - 1;
				p_last       = itr.p_node;
				p_last.next  = null;
			}
			p_size--;
			
			return p_node.data;
		}
		
		/**
		 * Löscht die Liste.
		 * 
		 * @see #pop()
		 */
		public function clear(): void {
			while (p_size != 0)
				this.pop();
		}
		
		/**
		 * Gibt die Anzahl der Items in der Liste zurück.<br />
		 * 
		 * @return Anzahl aller Items.
		 * 
		 * @see #isEmpty()
		 */
		public function size(): int { return p_size; }
		
		/**
		 * Gibt <i>true</i> zurück, falls die Liste leer ist, ansonsten <i>false</i>.
		 * 
		 * @return Ein boolescher Wert, ob die Liste leer ist.
		 * 
		 * @see #size()
		 */
		public function isEmpty(): Boolean { return p_size < 1; }
		
		/*
		08.08.2008:
			Mir fällt keine saubere Möglichkeit ein die Liste zyklisch zu gestalten.
			Schließlich soll man keinen Zugrif auf die internen List-Items haben und
			nur die Daten zurückbekommen!
			
			Die einzige möglichkeit wäre eine Funktion
			um ein Item hinzuzufügen, dass mit einem selbstbestimmten verlinkt ist.
			Danach müsste die Liste aber irgendwie abgeschlossen werden!
		
		public function hasLoop(): Boolean {
			if (this.size() < 2)
				return false;
			
			if (p_first == p_last)
				return true;
			
			// Implenetierung des Hase-Igel-Algorithums
			var igel: SLinkedListNode = p_first;
			var hase: SLinkedListNode = p_first.next;
			
			while (hase && igel != hase) {
				igel = igel.next;
				hase = hase.next;
				if (hase)
					hase = hase.next;
			}
			return !!hase;
		}
		*/
		
		/**
		 * Gibt den Index zurück, an dem das vorhanden ist.<br />
		 * Falls es nicht vorhanden ist, wird -1 zurück gegeben.
		 * 
		 * @param value Das zu suchende Objekt.
		 * 
		 * @return Der Index des ersten übereinstimmenden Items.
		 */
		public function contains(value: *): int {
			if (p_first.data == value)
				return 0;
			
			if (p_last.data == value)
				return this.size() - 1;
			
			p_node = p_first;
			
			var index: int = 0;
			while (p_node.hasNext() && ++index) {
				if (p_node.data == value)
					return index-1;
				
				p_node = p_node.next;
			}
			return -1;
		}
		
		/**
		 * Formatiert die Liste zu einem Array und gibt diesen zurück.
		 * 
		 * @return Ein Array mit allen Items.
		 * 
		 * @see #toString()
		 */
		public function toArray(): Array {
			var result: Array = [];
			p_node = p_first;
			
			while (p_node.hasNext() && result.push(p_node.data))
				p_node = p_node.next;
			result.push(p_last.data);

			return result;
		}
		
		/**
		 * Formatiert die Liste zu einem String und gibt diesen zurück.
		 * 
		 * @param delimiter Trennzeichen, dass nach jedem Item eingefügt wird.
		 * 
		 * @return Den formatierten String.
		 * 
		 * @see #toArray()
		 */
		public function toString(delimiter: String = ' '): String {
			return ArrayUtil.toString(this.toArray(), delimiter);
		}
	}
}



